package arithmetic;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;

/**
 * HJ28 素数伴侣
 * 描述
 * 知识点：
 * 1.获取偶数匹配奇数的组合，获取奇数匹配偶数的组合，输出两者中组合的最大值
 * 2.ArrayList.sort(Comparator.comparingInto(i -> i))
 * 3.判断一个数是否为质数，遍历除以从2到num/2的数据
 * 题目描述
 * 若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
 *
 * 输入:
 *
 * 有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
 *
 * 输出:
 *
 * 输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
 *
 *
 * 数据范围：1≤n≤100  ，输入的数据大小满足2≤val≤30000
 * 输入描述：
 * 输入说明
 * 1 输入一个正偶数 n
 * 2 输入 n 个整数
 *
 * 输出描述：
 * 求得的“最佳方案”组成“素数伴侣”的对数。
 *
 * 示例1
 * 输入：
 * 4
 * 2 5 6 13
 * 复制
 * 输出：
 * 2
 * 复制
 * 示例2
 * 输入：
 * 2
 * 3 6
 * 复制
 * 输出：
 * 0
 */
public class TestHW28 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int num = in.nextInt();
        if (num == 0)return;
        int[] nums = new int[num];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = in.nextInt();
        }
        if (nums.length == 2) {
            int num0 = nums[0] + nums[1];
            boolean f = primeTest(num0);
            if (f) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
            return;
        }
        oddAndEvenNum(nums);
    }

    public static void oddAndEvenNum(int[] nums) {
        //获取奇数数据，偶数数据
        ArrayList<Integer> oddList = new ArrayList<Integer>();
        ArrayList<Integer> evenList = new ArrayList<Integer>();
        int index = 0;
        while (index < nums.length) {
            int num = nums[index];
            if (num % 2 == 1) {
                oddList.add(num);
            } else {
                evenList.add(num);
            }
            index++;
        }
        //排序
        oddList.sort(Comparator.comparingInt(i -> i));
        evenList.sort(Comparator.comparingInt(i -> i));
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> hashMap1 = new HashMap<Integer, Integer>();
        int count1 = group(oddList, 0, evenList, hashMap);
        int count2 = group(evenList, 0, oddList, hashMap1);
        System.out.println(Math.max(count1, count2));
    }


    public static int group(ArrayList<Integer> oddList, int oddIndex,
                            ArrayList<Integer> evenList, HashMap<Integer, Integer> hashMap) {
        if (oddIndex >= oddList.size()) {
            return hashMap.size();
        }
        int odd = oddList.get(oddIndex);
        switchGroup(evenList, 0, odd, hashMap);
        oddIndex++;
        return group(oddList, oddIndex, evenList, hashMap);
    }

    public static boolean switchGroup(ArrayList<Integer> evenList,
                                      int start,
                                      int odd, HashMap<Integer, Integer> hashMap) {
        boolean f1 = false;
        for (int i = start; i < evenList.size(); i++) {
            int even = evenList.get(i);
            int add = even + odd;
            boolean f = primeTest(add);
            if (f) {
                if (hashMap.get(i) == null) {
                    hashMap.put(i, odd);
                    f1 = true;
                    break;
                } else {
                    int oddPre = hashMap.get(i);
                    f1 = switchGroup(evenList, i + 1, oddPre, hashMap);
                    if (f1) {
                        hashMap.put(i, odd);
                        break;
                    }
                }
            }
        }
        return f1;
    }


    //判断数字是否是素数
    public static boolean primeTest(int num) {
        boolean f = false;
        if (num == 2) {
            f = true;
            return f;
        }
        //num>2
        int end = num / 2;
        for (int i = 2; i <= end; i++ ) {
            if (num % i == 0) {
                f = false;
                break;
            } else {
                f = true;
            }
        }
        return f;
    }
}
